// 大根堆
function buildHeap(arr, len) {
    if(len === 1) return
    for(let i = Math.floor(len / 2); i > 0; i++) {
        heapify(arr, len, i)
    }
}
// len为元素个数
function heapify(arr, len, i) {
    while(true) {
        let minIndex = i
        if(2 * i <= len && arr[2 * i] < arr[i]) {
            minIndex = 2 * i
        }
        if(2 * i + 1 <= len && arr[2 * i + 1] < arr[minIndex]) {
            minIndex = 2 * i + 1
        }
        if(minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break;
        }
    }
}
function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}
class Heap {
    // arr前面有可能会放一个标志位，如果有的话，那么下面的获取父元素或者向下调整比较的索引应该相应改变
    constructor(compare) {
        this.compare = compare ? compare : (a, b) => a > b
        this.arr = []
    }
    get size() {
        return this.arr.size
    }
    // 插入元素
    push(num) {
        this.arr.push(num)
        // 向上调整
        this.siftUp(this.arr.length - 1)
    }
    siftUp(index) {
        let {arr, compare, parent} = this
        while(index > 0 && compare(arr[index], arr[parent(index)])) {
            this.swap(index, parent(index))
            index = parent(index)
        }
    }
    // 弹出堆顶元素
    pop() {
        if(this.arr.length === 0) return null
        this.swap(0, this.arr.length - 1)
        let n = this.arr.pop()
        this.siftDown(0)
    }
    // 向下调整
    siftDown(index) {
        let {arr, compare} = this
        while(true) {
            let tempInx = index
            let len = this.arr.length
            if(2 * index + 1 < len && compare(arr[2 * index + 1], arr[index]) ) {
                tempInx = 2 * index + 1
            }
            if(2 * index + 2 < len && compare(arr[2 * index + 2], arr[tempInx])) {
                tempInx = 2 * index + 2
            }
            if(tempInx === index) break
            this.swap(tempInx, index)
            index = tempInx
        }
    }
    // 获取父节点
    parent(index) {
        return Math.ceil(index / 2) - 1
    }
    swap(i, j) {
        [this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]]
    }
    // 获取堆顶元素
    peek() {
        return this.arr[0]
    }
}